
(define (accumulate f start more)
  (if (null? more)
      start
      (accumulate f (f start (car more)) (cdr more))))

(define (filter p l) (if (null? l) '() (if (p (car l)) (cons (car l) (filter p (cdr l))) (filter p (cdr l)))))

(define (flatmap f l) (accumulate (lambda (start more) (append start (f more))) '() l))

(define (enumerate-interval start stop)
  (if (= start stop)
      (cons start '())
      (cons start (enumerate-interval (+ start 1) stop))))

(define (list-ref l idx)
  (if (= idx 0)
      (car l)
      (list-ref (cdr l) (- idx 1))))

(define (abs x) (if (< x 0) (- 0 x) x))

;; stole from http://www.billthelizard.com/2011/06/sicp-242-243-n-queens-problem.html thanks bill

(define (make-position row col)
   (cons row col))

(define (position-row position)
   (car position))

(define (position-col position)
   (cdr position))

(define empty-board '())

(define (adjoin-position row col positions)
  (append positions (cons (make-position row col) '())))

(define (safe?-iter attacks? q board)
  (if (null? board)
      #t
      (if (not (attacks? q (car board)))
          (safe?-iter attacks? q (cdr board))
          #f)))

(define (safe? col positions)
  (let* ((kth-queen (list-ref positions (- col 1)))
         (other-queens (filter (lambda (q)
                                 (not (= col (position-col q))))
                               positions))
         (attacks? (lambda (q1 q2)
                     (if (= (position-row q1) (position-row q2))
                         #t
                         (= (abs (- (position-row q1) (position-row q2)))
                            (abs (- (position-col q1) (position-col q2))))))))
   (safe?-iter attacks? kth-queen other-queens)))

;;

(define (queen-cols board-size k)  
    (if (= k 0)
        (cons empty-board '())
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols board-size (- k 1))))))

(define (queens board-size)
  (queen-cols board-size board-size))

(define t1 (print (queens 8)))
